In contrast to traditional random-access data storage systems that write data to random-access storage structures, a conventional log-structured data storage system writes data into a sequential structure called a log which is stored in non-volatile memory. That is, the log is divided into a series of segments of equal size and, when the log-structured data storage system receives enough data to write a full segment, the log-structured data storage system writes that data into the next unoccupied segment. If any portion of that data had been written to an earlier-written segment in the series, the log-structured data storage system invalidates that portion of data in the earlier-written segment.
If all of the portions of data in an earlier-written segment become invalidated, the log-structured data storage system considers that earlier-written segment available for reuse. Additionally, the log-structured data storage system proactively consolidates valid data from partially-used segments (i.e., segments holding some valid portions of data and some invalidated portions of data) and stores the consolidated valid data in new segments thus freeing those partially-used segments for reuse.
Once the log-structured data storage system has written data to all of the segments in the log, the log-structured data storage system wraps around to the beginning of the series. The log-structured data storage system then writes data to the earlier-used segments which are now available for reuse.